package com.cjx.algorithm.sort;

import java.util.Arrays;

/**
 * @author cjx
 * @description 冒泡排序
 * @createDate 2024/4/11 14:58
 **/
public class Bubble {

    /**
     * 基础版
     * @param nums 待排序数组
     * @return 已排序数组
     */
    public int[] sortArray(int[] nums) {
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            for (int j = 1; j < length - i; j++) {
                if (nums[j] < nums[j-1]) {
                    //当前数小于前一个元素，二者交换
                    int temp = nums[j];
                    nums[j] = nums[j-1];
                    nums[j-1] = temp;
                }
            }
        }
        return nums;
    }

    /**
     * 优化版
     * @param nums 待排序数组
     * @return 已排序数组
     */
    public int[] sortArray2(int[] nums) {
        int length = nums.length;
        // 记录最后一次交换的位置，初始值为数组最后一个位置
        int lastSwapIndex = length;
        for (int i = 0; i < length; i++) {
            // 用于记录每次循环中的最后一次交换位置
            int newLastSwapIndex = 0;
            for (int j = 1; j < lastSwapIndex; j++) {
                if (nums[j] < nums[j-1]) {
                    //当前数小于前一个元素，二者交换
                    int temp = nums[j];
                    nums[j] = nums[j-1];
                    nums[j-1] = temp;
                    // 更新最后一次交换的位置
                    newLastSwapIndex = j;
                }
            }
            // 将新的最后一次交换位置更新为右边界
            lastSwapIndex = newLastSwapIndex;
            // 如果没有发生交换，说明数组已经有序，直接跳出循环
            if (newLastSwapIndex == 0) {
                break;
            }
        }
        return nums;
    }
}
